# Given an undirected weighted graph as an adjacency (numpy) matrix,
# find the maximum weighted spanning tree of the graph.

# This assumes the graph is undirected/symmetric (and uses the upper triangle).
# It also assumes the graph is connected (i.e., we are not looking for a forest).

# The algorithm is rather naive, O(n^2), i.e., it just scans the matrix.

# It returns the edges in the maximum spanning tree.

import numpy as np

class MaximumSpanningTreeFinder:

    def __init__(self):
        # nothing
        pass

    def find(self, graph):
        # we will always have n-1 edges
        edges = np.zeros( (len(graph) - 1, 2), dtype=np.int64 )

        # and keep track of the connected components
        vertexComponents = np.zeros( len(graph), dtype=np.int64 )
        for i in range(len(graph)):
            vertexComponents[i] = i


        for i in range( len(graph) - 1 ):
            maxVal = 0
            maxX = -1
            maxY = -1
            for x in range(len(graph)):
                for y in range(x+1, len(graph)):
                    # make sure we do not create a cycle
                    if vertexComponents[x] == vertexComponents[y]:
                        continue

                    if graph[x, y] > maxVal:
                        maxVal = graph[x, y]
                        maxX = x
                        maxY = y

            # update everything in the same component as Y to be in the component for X
            oldYcomponent = vertexComponents[maxY]
            for j in range(len(graph)):
                if vertexComponents[j] == oldYcomponent:
                    vertexComponents[j] = vertexComponents[maxX]
            edges[i, 0] = maxX
            edges[i, 1] = maxY


        return edges

